package msb.class01;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

/**
 * 局部最小值问题
 * 定义何为局部最小值：
 * arr[0] < arr[1]，0位置是局部最小；
 * arr[N-1] < arr[N-2]，N-1位置是局部最小；
 * arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；
 * 给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回
 */
public class Code07_BSAwesome {

    public static int minIndex(int[] arr) {
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            }
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
                continue;
            }
            if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
                continue;
            }
        }
        return L;
    }


    public static boolean checkMin(int[] arr, int index) {
        if (index == 0) {
            return arr[0] < arr[1];
        }
        if (index == arr.length - 1) {
            return arr[index] < arr[index - 1];
        }
        return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
    }


    @Test
    public void check() {
        int count = 10000;
        for (int i = 0; i < count; i++) {
            int[] arr = ArrayUtil.instantDistinct(50, 100);
            int index = minIndex(arr);
            Assert.assertTrue(checkMin(arr, index));
        }
    }

}
